/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ${USER}
 * Date: ${YEAR}-${MONTH}-${DAY}
 * Time: ${TIME}
 */
//public class Main {
//    public static void main(String[] args) {
//        System.out.println("Hello world!");
//    }
//}


class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newhead = new ListNode();
        ListNode cur = newhead.next;
        ListNode po1 = list1;
        ListNode po2 = list2;

        while (po1 != null && po2 != null) {
            if (po1.val <= po2.val) {
                cur = po1;
                po1 = po1.next;
            } else {
                cur = po2; // 同上
                po2 = po2.next;
            }
            cur = cur.next;
        }



        if(po1 == null){
            cur=po2;
        }
        if (po2 == null) {
            cur=po1;
        }


        return newhead.next;
    }

    public static void main(String[] args) {
        ListNode list1 = new ListNode(1);
        ListNode list3 = new ListNode(2);
        ListNode list4 = new ListNode(4);
        ListNode list2 = new ListNode(1);
        ListNode list21 = new ListNode(3);
        ListNode list22 = new ListNode(4);
        list1.next=list3;
        list3.next = list4;
        list2.next = list21;
        list21.next = list22;
        mergeTwoLists(list1, list2);

    }
}